#!/usr/bin/env python
#-*- coding:utf-8 -*-

food = {}
data = []

data_count = 0
item_count = 0 

def load_test_data():
    global food
    global data
    global data_count
    global item_count

    food = {
        0 : "面包", 
        1 : "牛奶", 
        2 : "尿布", 
        3 : "啤酒",
        4 : "鸡蛋", 
        5 : "可乐"
    }
    data = [
        (0, 1), 
        (0, 2, 3, 4), 
        (1, 2, 3, 5), 
        (0, 1, 2, 3), 
        (0, 1, 2, 5)
    ]
    data_count = len(data)
    item_count = len(food)

def load_data():
    global food
    global data
    global data_count
    global item_count
    print "prepare data...\n"

    item_dict = open("item_dict.txt")
    d_lines = item_dict.readlines()
    for line in d_lines:
        line = line.strip("\n")
        fields = line.split("\t")
        food[int(fields[0])] = fields[1]

    item_dict.close()

    item_trans = open("item_trans.txt")
    t_lines = item_trans.readlines()
    for line in t_lines:
        line = line.strip("\n")
        fields = line.split("\t")
        fields = [int(item) for item in fields]
        data.append(fields)

    data_count = len(data)
    item_count = len(food)

#计算频繁3项集，根据组合C63，应该有20个3项集，然后计算它们的支持度

def gen_n_item(n, items):
    def comb(items, n):
        for i in range(len(items)):
            v = items[i:i+1]
            if n == 1:
                yield v
            else:
                rest = items[i+1:]
                for c in comb(rest, n-1):
                    yield v + c

    result = []
    for item in comb(items, n):
        result.append(item)

    return result

def calc_support(result):
    support = [0] * len(result)
    for i in range(len(result)):
        item = set(result[i])
        for d in data:
            if item <= set(d):
                support[i] += 1    
        support[i] = float(support[i]) / data_count
    return support

def filter_support(support, threshold, full_items):
    support_dict = {}
    for i in range(len(support)):
        if support[i] >= threshold:
            support_dict.setdefault(support[i], [])
            support_dict[support[i]].append(full_items[i])
    numbers = support_dict.keys()
    numbers.sort()
    return dict([(number, support_dict[number]) for number in numbers])

def translate_result(items_dict):
    result = {}
    for k, v in items_dict.items():
        for indexes in v:
            items = " ".join([food[i] for i in indexes])
            result[items] = k
    return result
    
# 全组合
def gen_freq_items(n, items, threshold):
    full_items = gen_n_item(n, items)
    support = calc_support(full_items)
    filtered = filter_support(support, threshold, full_items)
    return translate_result(filtered)

#############
# use Apriori
def gen_cross_items(items1, items2):
    result = []
    for item1 in items1:
        for item2 in items2:
            nitem = item1 + item2
            if set(nitem) != set(item1) and (set(nitem) not in result):
                result.append(set(nitem))
    return [list(i) for i in result]

def platize(items):
    plat = []
    for item in items:
        for i in item:
            plat.append(i)
    return plat

def gen_freq_items_apriori(n, items, threshold):
    # 产生频繁1项集
    nitems = [[i] for i in items]
    support_one = calc_support(nitems)
    filtered = filter_support(support_one, threshold, nitems)
    if n==1:
        return translate_result(filtered)

    freq_one = platize(filtered.values())
    init = platize(filtered.values())
    count = 1
    # 这里使用F(k-1) x F1 的产生算法
    while (count < n):
        init = gen_cross_items(init, freq_one)
        support =  calc_support(init)
        filtered = filter_support(support, threshold, init)
        init = platize(filtered.values())
        count += 1
    
    return filtered, translate_result(filtered)

# cal confidence
def cal_conf(x, y, result):
    x_and_y_count = 0
    x_count = 0
    s_xandy = set(x+y)
    s_x = set(x)
    for res in result:
        if s_xandy <= set(res):
            x_and_y_count += 1
        if s_x <= set(res):
            x_count += 1
    
    return float(x_and_y_count)/x_count
    
    
def gen_conf_rules(items, conf, result):
    conf_items = []    
    # gen conf 1 item
    for i in range(len(items)):
        conf_res = [items[i]]
        conf_rule = list(set(items) - set(conf_res))
        confidence = cal_conf(conf_rule, conf_res, result)
        if confidence >= conf:
            conf_items.append([conf_rule, conf_res, confidence])

    def gen_conf_items(conf_temp):
        confs = []
        for i in range(len(conf_temp)):
            rulei, resi, confi = conf_temp[i]
            for j in range(i+1, len(conf_temp)):
                rulej, resj, confj = conf_temp[j]
                res = set(resi) | set(resj)
                rule = set(rulei) & set(rulej)
                if len(res)==0 or len(rule)==0:
                    continue
                confidence = cal_conf(list(rule), list(res), result)
                if confidence >= conf:
                    confs.append([list(rule), list(res), confidence])

        return confs
    
    temp = conf_items
    while 1:
        temp = gen_conf_items(temp)
        if not temp: break
        conf_items.extend(temp)
        if len(temp[0][0])==1: break
    
    return conf_items

if __name__ == "__main__":
    load_test_data()
    """
    print "User full items"
    print "-" * 20
    filtered, result =  gen_freq_items(3, range(item_count), 0.4)
    for k, v in result.items():
        print k, "==>", v
    load_data()
    """
    print "Use Apriori"
    print "Concalate Support"
    print "-" * 20
    #filtered, result =  gen_freq_items_apriori(2, range(item_count), 0.001)
    filtered, result =  gen_freq_items_apriori(3, range(item_count), 0.4)
    for k, v in result.items():
        print k, "==>", v
    
    print ""
    print "Concalate Confidence"
    print "-" * 20
    for items in filtered.values():
        for i in items:
            conf_items = gen_conf_rules(i, 0.6, data)
            for ci in conf_items:
                rules, res, conf = ci
                text_rules = " ".join("%s%s"%(j,food[j]) for j in rules)
                text_res = " ".join("%s%s"%(j, food[j]) for j in res)
                print text_rules, "==>", text_res, "[Conf:%s]"%(conf)
